import time


# 素数判断模块 改进版2 找到一个非平凡因子（[2,sqrt(n)]之间的因子）就退出
def prime(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, n, 2):
        if i * i > n: break
        if n % i == 0:
            return False
    return True


# 验证哥德巴赫猜想，对于大于6的每一个偶数n都可以分解成两个素数p,q，满足 p+q=n 约定p<=q O(N^2.5)
def goldbach(N):
    for n in range(6, N + 1, 2):
        flag = False  # 先假设n不能分解成两个素数
        for p in range(3, n, 2):
            q = n - p
            if p > q: break
            if prime(p) and prime(q) and p + q == n:
                flag = True  # n确实可以分解成素数p,q
                break
        if not flag:
            print(n, flag)
    #print('Bye!!')


for k in range(1, 7):
    n = 10 ** k
    start = time.time()
    goldbach(n)
    end = time.time()
    print(f"T({n})={end - start}")
